/*
 * @lc app=leetcode.cn id=68 lang=javascript
 *
 * [68] 文本左右对齐
 */

// @lc code=start
/**
 * @param {string[]} words
 * @param {number} maxWidth
 * @return {string[]}
 */
function fullJustify(words, maxWidth) {
  const result = []; // 存储最终结果
  let index = 0; // 当前处理的单词索引
  const n = words.length; // 单词总数

  while (index < n) {
    // 1. 选择当前行的单词
    let totalChars = 0; // 当前行的字符总数
    const start = index; // 当前行的起始单词索引

    // 贪心选择：尽可能多地放置单词
    while (
      index < n &&
      totalChars + words[index].length + (index - start) <= maxWidth
    ) {
      totalChars += words[index].length;
      index++;
    }

    // 2. 构建当前行
    let line = "";
    const numWords = index - start; // 当前行的单词数
    const numSpaces = maxWidth - totalChars; // 当前行需要的空格总数

    if (index === n || numWords === 1) {
      // 最后一行或只有一个单词：左对齐
      for (let i = start; i < index; i++) {
        line += words[i];
        if (i < index - 1) line += " ";
      }
      // 右侧填充空格
      line += " ".repeat(maxWidth - line.length);
    } else {
      // 非最后一行：均匀分配空格
      const avgSpaces = Math.floor(numSpaces / (numWords - 1)); // 平均每个间隔的空格数
      let extraSpaces = numSpaces % (numWords - 1); // 需要额外分配的空格数

      for (let i = start; i < index; i++) {
        line += words[i];
        if (i < index - 1) {
          // 分配平均空格
          line += " ".repeat(avgSpaces);
          // 分配额外空格
          if (extraSpaces > 0) {
            line += " ";
            extraSpaces--;
          }
        }
      }
    }

    // 3. 将当前行加入结果
    result.push(line);
  }

  return result;
}
// @lc code=end
